package 面试常见刷题;

import java.util.Arrays;

public class 归并排序 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{1, 2, 13, 1, 4})));
    }

    public static int[] mergeSort(int[] values) {
        if ( values.length<2) return values;
        int mid = values.length >> 1;
        int[] left = Arrays.copyOfRange(values,0,mid);
        int[] right = Arrays.copyOfRange(values,mid,values.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, index_left = 0, index_right = 0; index < result.length; index++) {//开始合并
            if (index_left >= left.length) {//左边的序列已经全部合并到了结果中，则直接将右边的序列合并到结果中
                result[index] = right[index_right++];
            } else if (index_right >= right.length) {//右边的序列已经全部合并到了结果中，则直接将左边的序列合并到结果中
                result[index] = left[index_left++];
            } else if (left[index_left] < right[index_right]) {//判断左边序列和右边序列当前要合并的元素的大小，保证合并的后的结果依然有序
                result[index] = left[index_left++];
            } else {
                result[index] = right[index_right++];
            }
        }
        return result;
    }
}
